#include <stdio.h>
#include <vector>
#include <iostream>
using namespace std;

int searchLastOne(vector<int> &nums) {
    int head = 0, tail = nums.size(), mid, cnt = 0;
    while(head < tail) {
        cout << cnt++ << endl;
        mid = (head + tail + 1) / 2;
        cout << "head : " << head << " , tail : " << tail << ", mid : " << mid << endl;
        if(nums[mid] == 0) tail = mid - 1;
        if(nums[mid] == 1) head = mid;
        cout << "head : " << head << " , tail : " << tail << ", mid : " << mid << endl;
    }
    cout << "result" << endl;
    cout << "head : " << head << " , tail : " << tail << ", mid : " << mid << endl;
    return head;
}

int main() {
    vector<int> nums{1, 1, 1,  1, 1, 0, 0, 0, 0};
    for(auto x : nums) {
        cout << x << " ";
    } 
    cout << endl;
    cout << searchLastOne(nums);
    cout << endl;
    return 0;
}